package HOT;

/**
 * Author  zxy
 * Date  2023/8/3 15:19
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeIntervals {

    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        // 对区间数组按照起始位置进行排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> mergedIntervals = new ArrayList<>();
        int[] currentInterval = intervals[0];

        for (int i = 1; i < intervals.length; i++) {
            if (currentInterval[1] >= intervals[i][0]) {
                // 当前区间和下一个区间有重叠，更新当前区间的结束位置
                currentInterval[1] = Math.max(currentInterval[1], intervals[i][1]);
            } else {
                // 当前区间和下一个区间没有重叠，将当前区间加入合并结果中
                mergedIntervals.add(currentInterval);
                currentInterval = intervals[i];
            }
        }

        // 最后一个区间还未添加
        mergedIntervals.add(currentInterval);

        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }

    public static void main(String[] args) {
        MergeIntervals mergeIntervals = new MergeIntervals();
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] merged = mergeIntervals.merge(intervals);

        for (int[] interval : merged) {
            System.out.println(Arrays.toString(interval));
        }
    }
}
